Common techniques for image compression, such as MPEG and JPEG, rely on blocked transforms. Though good for compression, these standard methods do not offer robust reconstruction techniques. Real world images tend to concentrate most of their energy in the low frequency bands. That is, most of the information content is stored in the low frequency coefficients of the transformed image. Packing this information into these relatively few coefficients has proved advantageous in image compression algorithms. Providing that these low frequency coefficients are transmitted correctly, an image can be recovered with high fidelity.
However, the cost of transforming an N-by-N image segment to or from the frequency domain requires approximately 2 N3 operations. If N is large, this becomes infeasible. To keep the complexity manageable, N is usually chosen to be a small number, e.g. 8, and the image is transformed one block at a time. In this way, the number of operations grows only linearly with the size of the image.
Block transforms which are also unitary are particularly attractive for transform encoding of an image because the mean-square contribution of a coefficient in the frequency domain equals its mean-square contribution in the time domain. For the encoder, this means that the larger a coefficient's magnitude is in the frequency domain, the larger its contribution to the time domain reconstruction. In the same way, errors in the frequency domain correspond in magnitude to errors in the time domain.
One drawback of the conventional transform encoding methods is that they are not robust to errors. This lack of robustness is partially attributable to the variable length methods of compression usually used in the encoding, and partially attributable to the lack of correlation between components in the frequency domain. The loss of synchronization due to variable length coding can be overcome by adding resynchronization points, or by using a pseudo-fixed length encoding. However, the lack of correlation in the frequency domain is a more fundamental problem that has not been adequately addressed by conventional encoding methods.
Other researchers, notably Edward Chang and Keng-Kuan Lin, “Error Concealment and Reconstruction Schemes for Image Transmission on a Wireless Network,” Stanford University, March 1997 and Sheila S. Hemami, “Reconstruction-Optimized Lapped Orthogonal Transforms for Robust Image Transmission,” Cornell University, April 1996, have investigated the problem of lack of correlation in the frequency domain in the past. These researchers addressed this problem by estimating lost frequency components using weighted averages of corresponding components from surrounding blocks.
However, this process is fundamentally limited by the ever decreasing correlation encountered with increasing block size. For example, if the DC component is damaged, trying to estimate it by averaging surrounding DC coefficients is similar to estimating a lost pixel from a small image by averaging surrounding pixels. Because the image formed from the DC components is small compared to the original, the spatial correlation is low. Therefore, the averaging process is not effective.